//给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。 
//
// 假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。 
//
// 你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,4,2,2]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,1,3,4,2]
//输出：3
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,1]
//输出：1
// 
//
// 示例 4： 
//
// 
//输入：nums = [1,1,2]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 105 
// nums.length == n + 1 
// 1 <= nums[i] <= n 
// nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次 
// 
//
// 
//
// 进阶： 
//
// 
// 如何证明 nums 中至少存在一个重复的数字? 
// 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？ 
// 
// Related Topics 位运算 数组 双指针 二分查找 
// 👍 1461 👎 0

package com.cute.leetcode.editor.cn;
public class FindTheDuplicateNumber {
    public static void main(String[] args) {
        Solution solution = new FindTheDuplicateNumber().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 这个题目不一样了，这次是有n+1个数，其中有一个多余的
     * 不能改变原始数组的结构，且只能使用额外的O(1)空间复杂的
     * 暴力双重循环可以解决问题，时间复杂度O(n2)，测试案例超时了，真鸡儿贼
     *
     * 瞄到题解灵光一闪，既然所有的元素是1-n，那就可以按照元素作为下标进行访问，将访问过的元素置为-1
     * 遍历的时候，如果num[当前元素] == -1 ，说明当前元素就是重复的，直接返回就行了，否则将当前位置置为-1，在访问下一个位置
     * 注意下标为0的元素的访问情况，因为其他元素是无法指到0这个位置的，所以对这个元素要额外判断一下
     *  例如5123456，此时如果没有一开始的判断，当index = 5的时候，会再次指向当前位置且不会返回，等下次会指向-1然后报错
     */
    public int findDuplicate(int[] nums) {

        /*for (int i = 0; i < nums.length ; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (j == i)continue;
                if (nums[i] == nums[j]) return nums[i];
            }
        }*/
        int index = 0;
        int temp = -1;
        while (true){
            if (nums[nums[index]] == nums[index] ) return nums[index];
            else if (nums[nums[index]] == -1) return nums[index];
            else {
                temp = index;
                index = nums[index];
                nums[temp] = -1;
            }
        }
    }

    /**
     * 题解是用的快慢指针，根据数组中的元素与下标i建立映射关系
     * 如果存在重复元素，那么按照当前映射关系的话一定存在环路，所以只需要找到环路的入口就行了
     * 在寻找入口的时候用到了快慢指针
     * 初始两个指针都是0，遍历的时候slow = nums[slow] fast = nums[nums[fast]]
     * 这样当slow == fast的时候就找到了环的入口
     * 然后再从0 和 slow进行循环遍历，直到两个值相等就是找到了重复元素
     * 这样不会破坏原始的nums结构！！！
     */
    public int findDuplicate2(int[] nums){
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow!=fast){
            slow = nums[slow];//slow一定会比fast慢到循环入口
            fast = nums[nums[fast]];
        }
        /*low = fast 时，快慢指针相遇，slow 走过的距离是初始点（0）到环状开始的点 （x） 加上 环状开始的点（x） 到相遇点（y） 这段距离
        而fast走过的距离是 初始点（0）到环状开始的点（x），点（x） 到点（y），点（y）到点（x），点（x）到点（y）。
        又因为fast走过的距离是low的两倍，设0到x长度为a，x到y长度为b,则有2*（a+b） = a+ b+ (y到x的距离) + b，则y到x的距离就等于0到x的距离。
        所以当新的两个指针 一个从0出发，一个从相遇点y出发时，他们走到的相同的值就是环状开始的点，即x点。*/
        fast = 0;
        while (fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}